/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-09
 * Time: 13:42
 */
import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
class Partition {
    public ListNode partition(ListNode pHead, int x) {
        //当pHead为空时
        if (pHead == null) {
            return null;
        }

        ListNode cur = pHead;
        ListNode prev = null;
        ListNode head1 = null;
        ListNode head2 = null;
        ListNode cur1 = null;
        ListNode cur2 = null;

        //遍历链表 将val < x的节点添加到新表head1中
        //将val >= x的节点添加到新表head2中
        while (cur != null) {
            if (cur.val < x) {
                if (head1 == null) {
                    head1 = cur1 = cur;
                }else {
                    cur1.next = cur;
                    cur1 = cur1.next;
                }
            }else {
                if (head2 == null) {
                    head2 = cur2 = cur;
                }else {
                    cur2.next = cur;
                    cur2 = cur2.next;
                }
            }
            cur = cur.next;
        }

        //注意：需要将head2的最后一个节点的next置为null
        if(head2 != null) {
            cur2.next = null;
        }
        //如果旧表中所有元素的val值都大于x，那么head1将会是空表，直接返回head2即可
        if (head1 == null) {
            return head2;
        }
        //将head1和head2进行拼接
        cur1.next = head2;
        return head1;
    }
}
public class Test {
}
